import random
from collections import OrderedDict

MEMORY_MAX_SIZE = 3
PAGE_NUMBER_MAX = 30
# 如果未提供PAGE_NUMBER，则使用随机生成的页面序列
PAGE_NUMBER = [
    7,
    0,
    1,
    2,
    0,
    3,
    0,
    4,
    2,
    3,
    0,
    3,
    2,
    1,
    2,
    0,
    1,
    7,
    0,
    1,
]
# 示例页面序列


class PageReplacementAlgorithm:
    def __init__(self, memory_size):
        self.memory_size = memory_size
        self.hit_count = 0

    def access_page(self, page_number):
        pass

    def get_hit_rate(self, total_pages):
        return self.hit_count / total_pages


class FIFOAlgorithm(PageReplacementAlgorithm):
    def __init__(self, memory_size):
        super().__init__(memory_size)
        self.memory = []
        self.queue = []

    def access_page(self, page_number):
        if page_number in self.memory:
            self.hit_count += 1
            print("Hit", end=" ")
        else:
            print("   ", end=" ")
            if len(self.memory) < self.memory_size:
                self.memory.append(page_number)
            else:
                oldest_page = self.queue.pop(0)
                self.memory.remove(oldest_page)
                self.memory.append(page_number)
            self.queue.append(page_number)
        print("FIFO_Memory:", self.memory, "PageNumber:", page_number)


class LRUAlgorithm(PageReplacementAlgorithm):
    def __init__(self, memory_size):
        super().__init__(memory_size)
        self.memory = OrderedDict()

    def access_page(self, page_number):
        if page_number in self.memory:
            self.hit_count += 1
            print("Hit", end=" ")
            # 将最近使用的页面移到末尾
            self.memory.move_to_end(page_number)
        else:
            print("   ", end=" ")
            if len(self.memory) >= self.memory_size:
                # 移除最久未使用的页面
                self.memory.popitem(last=False)
            self.memory[page_number] = None
        print("LRU_Memory:", list(self.memory.keys()), "PageNumber:", page_number)


class LFUAlgorithm(PageReplacementAlgorithm):
    def __init__(self, memory_size):
        super().__init__(memory_size)
        self.memory = {}
        self.page_counts = {}
        self.time_stamp = 0
        self.page_time = {}

    def access_page(self, page_number):
        self.time_stamp += 1
        if page_number in self.memory:
            self.hit_count += 1
            print("Hit", end=" ")
            self.page_counts[page_number] += 1
            self.page_time[page_number] = self.time_stamp
        else:
            print("   ", end=" ")
            if len(self.memory) >= self.memory_size:
                # 找到使用次数最少的页面
                min_count = min(self.page_counts.values())
                # 所有使用次数等于最小值的页面
                candidates = [
                    p for p in self.memory if self.page_counts[p] == min_count
                ]
                if len(candidates) > 1:
                    # 如果有多个，选择最久未使用的页面
                    oldest_time = min([self.page_time[p] for p in candidates])
                    lfu_page = None
                    for p in candidates:
                        if self.page_time[p] == oldest_time:
                            lfu_page = p
                            break
                else:
                    lfu_page = candidates[0]
                # 移除选中的页面
                del self.memory[lfu_page]
                del self.page_counts[lfu_page]
                del self.page_time[lfu_page]
            self.memory[page_number] = None
            self.page_counts[page_number] = 1
            self.page_time[page_number] = self.time_stamp
        print(
            "LFU_Memory:",
            list(self.memory.keys()),
            "PageNumber:",
            page_number,
            "Counts:",
            self.page_counts,
        )


def main():
    total_pages = len(PAGE_NUMBER)
    fifo = FIFOAlgorithm(MEMORY_MAX_SIZE)
    lru = LRUAlgorithm(MEMORY_MAX_SIZE)
    lfu = LFUAlgorithm(MEMORY_MAX_SIZE)

    for page_number in PAGE_NUMBER:
        fifo.access_page(page_number)
        lru.access_page(page_number)
        lfu.access_page(page_number)

    print("FIFO_HitRate:", fifo.get_hit_rate(total_pages))
    print("LRU_HitRate:", lru.get_hit_rate(total_pages))
    print("LFU_HitRate:", lfu.get_hit_rate(total_pages))


if __name__ == "__main__":
    main()
